// 笔试强训day29:最长上升子序列(二)

// 思路:
//新建一个数组，单调递增，数组中的数字upVec[i]表示长度为n的最小子序列，数组的长度就是最终子序列的长度。
//新来一个元素，如果他大于数组中的所有数字，则插入到末尾， 否则，把第一个大于他的数字变成他。 假设upVec = [1,3,5]， 如果来了7，则变成 [1,3,5,7],如果之后再来了2， 则变成[1,2,5,7]; （表示长度为2的子序列末尾最小值是2，因为他的前面只有1比他小）。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 该数组最长严格上升子序列的长度
     * @param a int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& a) {
        int n = a.size();
        vector<int> dp;
        for(int i = 0; i < n; i++)
        {
            if(dp.empty() || dp.back() < a[i])
            {
                dp.emplace_back(a[i]);
            }
            else 
            {
                int left = 0, right = dp.size() - 1, mid = 0;
                while(left <= right)
                {
                    mid = (left + right) >> 1;
                    if(dp[mid] == a[i])
                        break;
                    else if(dp[mid] < a[i])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
                if(dp[mid] < a[i])
                    mid++;
                dp[mid] = a[i];
            }
        }
        return dp.size();
    }
};